package main

// https://leetcode.cn/problems/sliding-window-maximum/
// maxSlidingWindow 计算数组中每个大小为 k 的滑动窗口的最大值。
// 参数:
//
//	nums: 输入的整数数组。
//	k: 滑动窗口的大小。
//
// 返回值:
//
//	包含每个滑动窗口最大值的数组。
func maxSlidingWindow(nums []int, k int) []int {
	// 获取输入数组的长度。
	n := len(nums)
	// 初始化结果数组，用于存储每个滑动窗口的最大值。
	ans := make([]int, 0)
	// 初始化双端队列，用于存储滑动窗口中潜在的最大值索引。
	dequeue := make([]int, 0)
	// 遍历输入数组。
	for i := 0; i < n; i++ {
		// 移除双端队列中所有小于当前元素的值，因为它们不可能成为滑动窗口的最大值。
		for len(dequeue) > 0 && nums[dequeue[len(dequeue)-1]] <= nums[i] {
			dequeue = dequeue[:len(dequeue)-1]
		}
		// 将当前元素的索引加入双端队列。
		dequeue = append(dequeue, i)
		// 判断是否已经形成了一个完整的滑动窗口。
		windowFormed := i >= k-1
		// 如果滑动窗口已形成且双端队列的第一个元素不在当前窗口内，则移除它。
		if windowFormed && dequeue[0] == i-k {
			dequeue = dequeue[1:]
		}
		// 如果滑动窗口已形成，则将双端队列的第一个元素（即当前窗口的最大值）加入结果数组。
		if windowFormed {
			ans = append(ans, nums[dequeue[0]])
		}
	}
	// 返回结果数组。
	return ans
}
